package de.pass.ch.datastr;

import static java.lang.Integer.MAX_VALUE;
import static de.pass.ch.util.Constants.SPECIAL_NODEID;

import de.pass.ch.util.Constants;

public class BinaryHeapNodeOrder {

	/**
	 * Level of the node. This is initially Integer.MAX_VALUE and will be set to
	 * the calculated level directly after the contraction of the node.
	 */
	private int[] levels;

	/**
	 * Size of the search spaces of the local searches. used as priority term to
	 * speedup the contraction.
	 */
	private int[] searchSpaces;

	/** deleted/contracted neighbors counter */
	private int[] deletedNeighbors;

	/**
	 * Upper bound on search paths found by the query algorithm. Datatype double
	 * is used since this bound is modified for time-dependend routing
	 * (parameter "-T")
	 */
	private double[] searchPathHopBorders;

	/**
	 * Those three variables are used for the priority term Voronoi regions.
	 * They allow to manage the Voronoi regions of the remaining nodes. The
	 * voronoi region that this node belongs to.
	 */
	private int[] voronoiOwners;

	/**
	 * The nodes in a voronoi region are stored in a linked list. The list is
	 * terminated by SPECIAL_NODEID.
	 */
	private int[] voronoiNextBorderNodes;

	/**
	 * Contains the number of nodes in the voronoi region if the nodes is not
	 * contracted. Otherwise, if the node is already contracted, it contains the
	 * distance to the voronoiOwner.
	 */
	private int[] voronoiNumbers;

	/**
	 * Keys of the binary heap. The Key of a node with id 'nodeID' is stored at
	 * keys[nodeID].
	 */
	private double[] keys;

	/**
	 * Indizes of the binary heap. The heap-index of a node with id 'nodeID' is
	 * stored at indizes[nodeID].
	 */
	private int[] indizes;

	/**
	 * Inverse Indizes to {@link #indizes}. The id of a node with heap-index i
	 * is stored at heapOrder[i].
	 */
	private int[] heapOrder;

	/** Number of elements, which are actually in the heap. */
	private int size;

	/**
	 * Constructor of the binary heap.<br>
	 * <b>Necessary: Parameter size is not changeable anymore.</b>
	 * 
	 * @param size
	 *            - Maximum size of the heap
	 */
	public BinaryHeapNodeOrder(int size) {

		this.size = 0;

		size++;

		levels = new int[size];
		searchSpaces = new int[size];
		deletedNeighbors = new int[size];
		searchPathHopBorders = new double[size];
		voronoiOwners = new int[size];
		voronoiNextBorderNodes = new int[size];
		voronoiNumbers = new int[size];

		for (int i = 0; i < size; i++) {
			levels[i] = MAX_VALUE;
			voronoiOwners[i] = SPECIAL_NODEID;
			voronoiNextBorderNodes[i] = SPECIAL_NODEID;
		}

		keys = new double[size];
		indizes = new int[size];
		heapOrder = new int[size];

		insertDummy();

	}

	/**
	 * Returns the actual number of elements in the heap.
	 * 
	 * @return number of elements in the heap
	 */
	public int size() {
		return size - 1;
	}

	private void insertDummy() {
		levels[size] = Integer.MAX_VALUE;
		searchSpaces[size] = 0;
		deletedNeighbors[size] = 0;
		searchPathHopBorders[size] = 0;
		voronoiOwners[size] = Constants.SPECIAL_NODEID;
		voronoiNextBorderNodes[size] = Constants.SPECIAL_NODEID;
		voronoiNumbers[size] = 0;
		indizes[size] = 0;
		keys[size] = Double.MAX_VALUE;
		heapOrder[size] = 0;
		size++;
	}

	/** Returns the external key of this element. */
	public double key(int nodeID) {
		return keys[nodeID + 1];
	}

	/** Sets the external key of this element. */
	public void key(int nodeID, double newKey) {
		keys[nodeID] = newKey;
	}

	/**
	 * 
	 * @param nodeID
	 *            - ID of the node.
	 * @return true, if the heap element of the node nodeID is a Dummy-Element.
	 */
	public boolean isDummy(int nodeID) {
		return key(nodeID) == Double.MAX_VALUE;
	}

	/** Marks that this element has been deleted from the heap. */
	public void markDeleted(int nodeID) {
		index(nodeID, 0);
	}

	/** Returns true iff this element has been deleted from the heap. */
	public boolean hasBeenDeleted(int nodeID) {
		return (indizes[nodeID] == 0);
	}

	/** Returns this element's index within the heap. */
	private int index(int nodeID) {
		return indizes[nodeID];
	}

	/** Sets this element's index within the heap. */
	private void index(int nodeID, int newIndex) {
		indizes[nodeID] = newIndex;
	}

	/** Returns true iff the heap is empty. */
	public boolean empty() {
		return (size() == 0);
	}

	/**
	 * Returns the (external) key of the minimum element in this heap or the
	 * maximum value of the ExternalKey data type iff the heap is empty.
	 */
	public double min() {
		if (empty())
			return Double.MAX_VALUE;
		return (keys[heapOrder[1]]);
	}

	/**
	 * Creates a new element with the given (internal) key and inserts it into
	 * the heap.
	 * 
	 * @return the index of the new element.
	 */
	public int insert(double key, PQueueNodeElimination data) {
		int element = size;
		int index = size;
		insertElement(key, index, data);
		upheap(index);
		size++;
		return element;
	}

	/** Replaces a dummy element and inserts the actual element into the heap. */
	public void insert(double key, int elementIndex) {
		int index = size;
		key(elementIndex, key);
		index(elementIndex, index);
		heapOrder[size] = elementIndex;
		keys[heapOrder[size]] = key;
		size++;
		upheap(index);
	}

	private void insertElement(double key, int index, PQueueNodeElimination data) {
		levels[index] = data.level;
		searchSpaces[index] = data.searchSpace;
		deletedNeighbors[index] = data.deletedNeighbors;
		searchPathHopBorders[index] = data.searchPathHopBorder;
		voronoiOwners[index] = data.voronoiOwner;
		voronoiNextBorderNodes[index] = data.voronoiNextBorderNode;
		voronoiNumbers[index] = data.voronoiNumber;
		indizes[index] = index;
		keys[index] = key;
		heapOrder[index] = index;
	}

	/**
	 * Returns the index of the minimum element in this heap or 0 iff the heap
	 * is empty.
	 */
	public int minElement() {
		if (empty())
			return 0;
		return (heapOrder[1]);
	}

	/**
	 * Deletes the minimum element in this heap. Precondition: The heap is not
	 * empty.
	 * 
	 * @return the index of the deleted element
	 */
	public int deleteMin() {
		assert (!empty());
		int element = heapOrder[1];
		keys[heapOrder[1]] = Double.MAX_VALUE;
		int index = 1;
		int droppingElement = heapOrder[size - 1];
		heapOrder[size - 1] = 0;
		index(element, 0);
		heapOrder[index] = droppingElement;
		size--;
		if (size() > 1) {
			// downheap:
			// Move the element at the top downwards
			// until the heap condition is restored.
			double k = keys[heapOrder[index]];

			int nextIndex = 2 * index;
			while (nextIndex < size) {
				nextIndex += ((nextIndex + 1 < size) && (keys[heapOrder[nextIndex]] > keys[heapOrder[nextIndex + 1]])) ? 1
						: 0;

				// assert( _elements[_heap[nextIndex].first].key() ==
				// KeyExtractor::key(_heap[nextIndex].second) );

				if (k <= keys[heapOrder[nextIndex]])
					break;

				// keys[heapOrder[index]] = keys[heapOrder[nextIndex]];
				heapOrder[index] = heapOrder[nextIndex];
				index(heapOrder[nextIndex], index);
				index = nextIndex;
				nextIndex *= 2;
			}
			heapOrder[index] = droppingElement;
			keys[heapOrder[index]] = k;

			// end of downheap
		}
		index(droppingElement, index);

		markDeleted(element);
		// COUNTING(counter.incDouble(COUNT_DEL_MIN));
		return element;
	}

	/**
	 * Increases the key of the given element: sets the key to the given value.
	 */
	public void increaseKey(int element, double newKey) {
		int index = index(element);
		assert (index < size);
		assert (heapOrder[index] == element);

		key(element, newKey);
		keys[heapOrder[index]] = newKey;
		downheap(index);
		// COUNTING( counter.incDouble(COUNT_INCR_KEY) );
	}

	/**
	 * Decreases the key of the given element: sets the key to the given value.
	 */
	public void decreaseKey(int element, double newKey) {
		int index = index(element);
		assert (index < size);
		assert (heapOrder[index] == element);

		key(element, newKey);
		keys[heapOrder[index]] = newKey;
		upheap(index);
		// COUNTING( counter.incDouble(COUNT_DECR_KEY) );
	}

	/**
	 * Updates the key of the given element: sets the key to the given value.
	 * The key can be larger or smaller than the previous key.
	 */
	public void updateKey(int element, double newKey) {
		element++;
		int index = index(element);
		assert (index < size);
		assert (heapOrder[index] == element);
		double oldKey = keys[heapOrder[index]];

		keys[heapOrder[index]] = newKey;
		if (newKey < oldKey) {
			upheap(index);
			// COUNTING( counter.incDouble(COUNT_DECR_KEY) );
		} else if (newKey > oldKey) {
			downheap(index);
			// COUNTING( counter.incDouble(COUNT_INCR_KEY) );
		}
	}

	private void upheap(int index) {
		int risingElement = heapOrder[index];
		double k = keys[heapOrder[index]];
		while (keys[heapOrder[index / 2]] > k && index > 1) {
			assert (index > 1);
			// assert (keys[heapOrder[index / 2]] == keys[heapOrder[index /
			// 2]]);
			// keys[heapOrder[index]] = keys[heapOrder[index / 2]];
			heapOrder[index] = heapOrder[index / 2];
			index(heapOrder[index], index);
			index /= 2;
		}
		heapOrder[index] = risingElement;
		// keys[heapOrder[index]] = k;
		index(risingElement, index);
	}

	/**
	 * Move the element with the given index downwards. until the heap condition
	 * is restored.
	 */
	private void downheap(int index) {
		int descendingElement = heapOrder[index];
		double k = keys[heapOrder[index]];
		int maxIndex;
		if (2 * index < size && keys[heapOrder[2 * index]] < k) {
			maxIndex = 2 * index;
		} else {
			maxIndex = index;
		}
		if ((2 * index + 1) < size
				&& keys[heapOrder[2 * index + 1]] < keys[heapOrder[maxIndex]]) {
			maxIndex = 2 * index + 1;
		} else if ((2 * index + 1) < size && maxIndex == index
				&& keys[heapOrder[2 * index + 1]] < k) {
			maxIndex = 2 * index + 1;
		}
		while (maxIndex != index) {
			assert (index >= 1);
			// assert( _elements[_heap[maxIndex].first].key() ==
			// KeyExtractor::key(_heap[maxIndex].second) );
			// keys[heapOrder[index]] = keys[heapOrder[maxIndex]];
			heapOrder[index] = heapOrder[maxIndex];
			index(heapOrder[index], index);
			index = maxIndex;
			// keys[heapOrder[index]] = k;

			if (2 * index < size && keys[heapOrder[2 * index]] < k) {
				maxIndex = 2 * index;
			} else {
				maxIndex = index;
			}
			if ((2 * index + 1) < size
					&& keys[heapOrder[2 * index + 1]] < keys[heapOrder[maxIndex]]) {
				maxIndex = 2 * index + 1;
			} else if ((2 * index + 1) < size && maxIndex == index
					&& keys[heapOrder[2 * index + 1]] < k) {
				maxIndex = 2 * index + 1;
			}
		}
		heapOrder[index] = descendingElement;
		index(descendingElement, index);
	}

	/**
	 * For debugging purpose.
	 * 
	 * @return _heap is still a binary heap.
	 */
	public boolean checkHeapProperty() {
		boolean result = true;
		for (int i = 2; i < size; i++) {
			if (!(keys[heapOrder[i / 2]] <= keys[heapOrder[i]])) {

				System.out.print("key[" + (i / 2) + "] = "
						+ keys[heapOrder[i / 2]]);
				System.out.println(" > " + keys[heapOrder[i]] + " = key[" + i
						+ "]");

				result = false;
				break;
			}
		}
		return result;
	}

	public PQueueNodeElimination getPQData(int node) {
		node++;
		PQueueNodeElimination data = new PQueueNodeElimination();
		data.level = levels[node];
		data.searchSpace = searchSpaces[node];
		data.deletedNeighbors = deletedNeighbors[node];
		data.searchPathHopBorder = searchPathHopBorders[node];
		data.voronoiOwner = voronoiOwners[node];
		data.voronoiNextBorderNode = voronoiNextBorderNodes[node];
		data.voronoiNumber = voronoiNumbers[node];
		return data;
	}

	public void setLevel(int node, int level) {
		levels[node + 1] = level;
	}

	public void setSearchPathHopBorder(int node, double newsearchPathHopBorder) {
		searchPathHopBorders[node + 1] = newsearchPathHopBorder;
	}

	public void setDeletedNeighbors(int node, int newDeletedNeighbors) {
		deletedNeighbors[node + 1] = newDeletedNeighbors;
	}

	public void setSearchSpace(int node, int searchSpace) {
		searchSpaces[node + 1] = searchSpace;
	}
}
